package main

//func levelOrder(root *TreeNode)[]int{
//	res :=[]int{}
//	if root==nil{
//		return res
//	}
//	re11:=Bfs(root,res)
//	res1 :=Bfs(root.Right,re11)
//	res2 :=Bfs(root.Left,res1)
//	return res2
//}
//
//func Bfs(root *TreeNode,res []int)[]int{
//	if root ==nil{
//		return res
//	}
//	queue :=[]*TreeNode{root}
//	tmp :=queue
//	queue = nil
//	for len(queue) >0{
//		for i,v:=range tmp{
//			if i+1<len(tmp){
//				res=append(res,v.Val)
//			}
//			if v.Left !=nil{
//				queue =append(queue,v.Left)
//			}
//			if v.Right !=nil{
//				queue =append(queue,v.Right)
//			}
//		}
//	}
//
//	return res
//}

func levelOrder(root *TreeNode) [][]int {
	//最终要返回的res
	var res [][]int
	//利用栈将下层的节点进行收集
	var stack []*TreeNode
	stack = append(stack, root)
	//将一层所有的节点遍历完才输出
	for len(stack) != 0 {
		n := len(stack)
		var v []int
		for i := 0; i < n; i++ {
			//node取的是一层一个个往后，随着stack[:1],stack[0]也在不断改变
			node := stack[0]
			//用一层中不断缩小层规模
			stack = stack[1:]
			//将当前节点的下层左右节点也进行入栈
			if node != nil {
				//将当前节点的值放入一维数组中
				v = append(v, node.Val)
			}
			if node.Right != nil {
				stack = append(stack, node.Right)
			}
			if node.Left != nil {
				stack = append(stack, node.Left)
			}
			//将一维数组加入到最终返回的二维数组中

			if len(v) > 0 {
				res = append(res, v)
			}
		}

	}
	return res

}
//自己写的
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	stack := []*TreeNode{root}
	for len(stack) != 0 {
		var v []int
		n:=len(stack)
		for i := 0; i <n ; i++ {
			node := stack[0]
			stack = stack[1:]
			if node != nil {
				v = append(v, node.Val)
				if node.Left != nil {
					stack = append(stack, node.Left)
				}
				if node.Right != nil {
					stack = append(stack, node.Right)
				}
			}

		}
		if len(v) > 0 {
			res = append(res, v)
		}
	}
	return res
}
